package it.storm.solution;

import java.util.Stack;

/**
 * 962. 最大宽度坡
 * https://leetcode-cn.com/problems/maximum-width-ramp/
 */
public class Solutions_962 {
    public static void main(String[] args) {
        int[] nums = {6, 0, 8, 2, 1, 5};  // output: 4
//        解释：最大宽度的坡为 (i,  j) = (1,  5): A{1} = 0 且 A{5} = 5

//        int[] nums = {9, 8, 1, 0, 1, 9, 4, 0, 4, 1};  // output: 7
//        解释：最大宽度的坡为 (i,  j) = (2,  9): A{2} = 1 且 A{9} = 1

//        int[] nums = {2, 2, 1};  // output: 1

        int result = maxWidthRamp(nums);
        System.out.println(result);
    }

    /**
     * 解题思路：单调栈
     */
    public static int maxWidthRamp(int[] A) {
        int res = 0;
        // 创建单调递减栈（严格递减）
        int len = A.length;
        Stack<Integer> stack = new Stack<>();
        stack.add(0);

        for (int i = 1; i < len; i++) {
            if (!stack.isEmpty() && A[i] < A[stack.peek()]) {
                stack.add(i);
            }
        }
        for (int i = A.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && A[i] >= A[stack.peek()]) {
                // 索引 i 与 stack[idx - 1] 之间，存在坡
                int width = i - stack.pop();
                res = Math.max(res, width);
            }
            if (stack.isEmpty()) {
                break;
            }
        }
        return res;
    }
}
